package leetcode_500;

import java.util.Arrays;
import java.util.Comparator;

/**
 *@author 周杨
 *MinimumNumberOfArrowsToBurstBalloons_452 打气球游戏 给定一个二维数组代表气球的大小 求最小发射子弹能打爆所有气球的次数
 *describe:用贪心算法 根据气球的覆盖排序  局部最优解等于全局最优解  AC 63%
 *2018年8月24日 下午2:39:01
 */
public class MinimumNumberOfArrowsToBurstBalloons_452 {
	public static void main(String[] args) {
		MinimumNumberOfArrowsToBurstBalloons_452 test=new MinimumNumberOfArrowsToBurstBalloons_452();
		int [][]points=new int[][] {{10,16},{2,8},{1,6},{7,12}};
		System.out.println(test.findMinArrowShots(points));
	}
	
	
	public int findMinArrowShots(int[][] points) {
		if(points.length==0||points[0].length==0)
			return 0;
	      Arrays.sort(points, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[0]>o2[0])
					return 1;
				if(o1[0]==o2[0])
					if(o1[1]==o2[1])
						return 0;
					else if(o1[1]>o2[1])
						return 1;
					else
						return -1;
				return -1;
			}
		});
	    int res=1,end=points[0][1];
	    for(int i=1;i<points.length;++i) {
	    	if(points[i][0]>end) {
	    		++res;
	    		end=points[i][1];
	    	}
	    	else {
	    		end=Math.min(end, points[i][1]);
	    	}
	    }
	    return res;
	}
}
